package salesforce.sortanarray;

import java.util.Arrays;

//即可以前，也可以后
//https://www.geeksforgeeks.org/count-minimum-number-of-moves-to-front-or-end-to-sort-an-array/
public class SortAnArray {
    // Function that counts the minimum
// moves required to covert arr[] to brr[]
    static int minOperations(int arr1[], int arr2[],
                             int i, int j)
    {

        // Base Case
        if (arr1.equals(arr2)){
            System.out.println("i:" + i + " j:" + j + " =" + 0);
            return 0;
        }


        if (i >= arr1.length || j >= arr2.length) {
            System.out.println("i:" + i + " j:" + j + " =" + 0);
            return 0;
        }

        // If arr[i] < arr[j]
        if (arr1[i] < arr2[j]) {
            System.out.println("i:" + i + " j:" + j + " = 1 + minOperations(" + (i+ 1) + ", " + (j+1)+ ")" );
            // Include the current element
            return 1 + minOperations(arr1, arr2,
                    i + 1, j + 1);
        }


        System.out.println("i:" + i + " j:" + j + " = max((i:" + i  + " j:" + (j+1) + "), (i:" + (i+1) + " j:" + j +")");
        // Otherwise, excluding the current element
        return Math.max(minOperations(arr1, arr2,
                i, j + 1),
                minOperations(arr1, arr2,
                        i + 1, j));
    }

    // Function that counts the minimum
// moves required to sort the array
    static void minOperationsUtil(int[] arr)
    {
        int brr[] = new int[arr.length];

        for(int i = 0; i < arr.length; i++)
            brr[i] = arr[i];

        Arrays.sort(brr);

        // If both the arrays are equal
        if (arr.equals(brr))

            // No moves required
            System.out.print("0");

            // Otherwise
        else

            // Print minimum operations required
            System.out.println(minOperations(arr, brr,
                    0, 0));
    }

    // Driver code
    public static void main(final String[] args)
    {
        // int arr[] = { 4, 7, 2, 3, 9 };

        int arr[] = {1,2,8,4,7,100};

        minOperationsUtil(arr);
    }
}
